package strings;

/**
 * @Author: pengfei.hpf
 * @Date: 2020/1/27
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 *
 * 输入为非空字符串且只包含数字 1 和 0。
 *
 * 示例 1:
 *
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 示例 2:
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-binary
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class AddBinary {
    public String addBinary(String a, String b) {
        if(a == null || a.length() == 0){
            return b;
        }
        if(b == null || b.length() == 0){
            return a;
        }
        if(a.length() > b.length()){
            String s = b;
            b = a;
            a = s;
        }
        int m = a.length() - 1;
        int n = b.length() - 1;
        StringBuilder res = new StringBuilder();
        int carry = 0;
        while(n >= 0){
            int c1 = 0;
            if(m >= 0) {
                c1 = a.charAt(m) - '0';
            }
            int c2 = b.charAt(n) - '0';
            int sum = c1 + c2 + carry;
            if(sum >= 2){
                carry = 1;
            } else {
                carry = 0;
            }
            res.insert(0, sum % 2);
            n--;
            m--;
        }
        if(carry == 1){
            res.insert(0, 1);
        }
        return res.toString();
    }
}
